BZOJ1052【HAOI2007】覆盖问题 <二分答案>

Problem

【HAOI2007】覆盖问题

Description

某人在山上种了棵小树苗。冬天来了，温度急速下降，小树苗脆弱得不堪一击，于是树主人想用一些塑料薄膜把这些小树遮盖起来，经过一番长久的思考，他决定用个的正方形塑料薄膜将小树遮起来。我们不妨将山建立一个平面直角坐标系，设第棵小树的坐标为，个的正方形的边要求平行与坐标轴，一个点如果在正方形的边界上，也算作被覆盖。当然，我们希望塑料薄膜面积越小越好，即求L最小值。

Input

第一行有一个正整数，表示有多少棵树。
接下来有行，第行有个整数，表示第棵树的坐标，保证不会有个树的坐标相同。

Output

一行，输出最小的值。

Sample Input

Sample Output

HINT

的数据，

标签：二分答案

Solution

二分水题。

考虑到当大于等于答案时，一定能全部覆盖。因此可以二分答案。
对于当前二分到的答案，贪心选取前两个正方形，然后判断剩下的点能否被一个正方形包住。
贪心选取即每个正方形一定覆盖剩余点中左上、左下、右上、右下四个最远点中至少一个，因而枚举种情况后判断即可。

Code

#include <bits/stdc++.h>
#define x first
#define y second
#define mp make_pair
#define pii pair<int,int>
#define MAX_N 20000
#define INF 0x3f3f3f
#define mid ((l+r)>>1)
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n;	pii p[MAX_N+5];	bool mrk[MAX_N+5];
bool chk(int r) {
    int x1 = INF, y1 = INF, x2 = -INF, y2 = -INF;
    for (int i = 1; i <= n; i++) if (!mrk[i])
        x1 = min(x1, p[i].x), y1 = min(y1, p[i].y), 
        x2 = max(x2, p[i].x), y2 = max(y2, p[i].y);
    return x2-x1 <= r && y2-y1 <= r;
}
int del(int sx, int sy, int r) {
    int ret = 0;
    for (int i = 1; i <= n; i++) if (!mrk[i])
        if (p[i].x >= sx && p[i].x <= sx+r) 
            if (p[i].y >= sy && p[i].y <= sy+r)
                mrk[i] = true, ret++;
    return ret;
}
bool DFS(int stp, int lft, int r) {
    if (!lft) return true;
    if (stp > 2) return chk(r);
    int x1 = INF, y1 = INF, x2 = -INF, y2 = -INF;
    for (int i = 1; i <= n; i++) if (!mrk[i])
        x1 = min(x1, p[i].x), y1 = min(y1, p[i].y), 
        x2 = max(x2, p[i].x), y2 = max(y2, p[i].y);
    bool bk[MAX_N+5];	memcpy(bk, mrk, sizeof mrk);
    if (DFS(stp+1, lft-del(x1, y1, r), r)) return true;		memcpy(mrk, bk, sizeof bk);
    if (DFS(stp+1, lft-del(x1, y2-r, r), r)) return true;	memcpy(mrk, bk, sizeof bk);
    if (DFS(stp+1, lft-del(x2-r, y1, r), r)) return true;	memcpy(mrk, bk, sizeof bk);
    if (DFS(stp+1, lft-del(x2-r, y2-r, r), r)) return true;	memcpy(mrk, bk, sizeof bk);
    return false;
}
int bi_search(int l, int r) {
    int ret = -1;
    while (l <= r) {
        memset(mrk, false, sizeof mrk);
        if (!DFS(1, n, mid)) l = mid+1;
        else ret = mid, r = mid-1;
    }
    return ret;
}
int main() {
    read(n);
    for (int i = 1; i <= n; i++) read(p[i].x), read(p[i].y);
    return printf("%d\n", bi_search(1, INF)), 0;
}